#include <iostream>
#include <vector>
using namespace std;

class Solution {
  public:
    int findMin(vector<int>& nums) {
        if (nums.front() < nums.back()) return nums.front();
        int low = 0, high = nums.size() - 1;
        while (high > low) {
            auto mid = (high + low) / 2;
            if (nums[mid] > nums[high])
                low = mid + 1;
            else if (nums[mid] < nums[high])
                high = mid;  // maybe min = nums[mid]
            else
                --high;
            // mid < high, if min = nums[high], nums[high-1] == nums[high]
            // if min != nums[high], nums[high-1] <= nums[high]
        }
        return nums[high];
    }
};

int main() {
    std::vector<int> nums{3, 3, 1, 3, 3, 3, 3};
    Solution s;
    s.findMin(nums);
}
